package com.salim.leetcode.$76;


public class MinimumWindowSubstring {
    //方法1 超时了
    //先缩左 缩到不能缩缩右 得到第一个缩小的范围
    //再用这个范围遍历 寻找下一个合适的区间并再次缩小范围
    //字符串范围英文26个字母大小写 65-90 97-122 0-25 32-57
    //方法2 双指针从左往右
    //当第一次出现条件符合的字符串时 记录长度
    //1.移动左边直至不符合
    //2.移动右边直至符合 记录长度 并再次试图移动左边至最小合规 记录长度
    //重复1、2
//    public String minWindow(String s, String t) {
//        String result = s;
//        int[] sArray = new int[58];
//        int[] tArray = new int[58];
//        initArray(sArray,s);
//        initArray(tArray,t);
//        int left = 0;
//        int right = s.length()-1;
//        //全检查
//        for(int i=0;i<58;i++){
//            if(tArray[i]>sArray[i]){
//                return "";
//            }
//        }
//        while (left<right){
//            if(sArray[s.charAt(left)-65]-1<tArray[s.charAt(left)-65]){
//                break;
//            }
//            sArray[s.charAt(left)-65]--;
//            left++;
//        }
//        while (left<right){
//            if(sArray[s.charAt(right)-65]-1<tArray[s.charAt(right)-65]){
//                break;
//            }
//            sArray[s.charAt(right)-65]--;
//            right--;
//        }
//        result = s.substring(left,right+1);
//
//        int originLeft = left;
//        int originRight = right;
//        int[] originSArray = sArray.clone();
//        //向右平移
//        while (right+1<s.length()){
//            sArray[s.charAt(left)-65]--;
//            sArray[s.charAt(right+1)-65]++;
//            if(sArray[s.charAt(left)-65]<tArray[s.charAt(left)-65]
//                ||sArray[s.charAt(right+1)-65]<tArray[s.charAt(right+1)-65]){
//            }else if(tArray[s.charAt(left)-65]>0 || tArray[s.charAt(right+1)-65]>0){
//                String subResult = minWindow(s.substring(left+1,right+2),t);
//                if(!subResult.equals("")&&subResult.length()<result.length()){
//                    result = subResult;
//                }
//            }
//            left++;
//            right++;
//        }
//
//        if(right+1-left<result.length()){
//            result = s.substring(left,right+1);
//        }
//
//        left = originLeft;
//        right = originRight;
//        sArray = originSArray;
//        //向左平移
//        while (left>0){
//            sArray[s.charAt(right)-65]--;
//            sArray[s.charAt(left-1)-65]++;
//            if(sArray[s.charAt(right)-65]<tArray[s.charAt(right)-65]
//                ||sArray[s.charAt(left-1)-65]<tArray[s.charAt(left-1)-65]){
//            }else if(tArray[s.charAt(right)-65]>0 || tArray[s.charAt(left-1)-65]>0){
//                String subResult = minWindow(s.substring(left-1,right),t);
//                if(!subResult.equals("")&&subResult.length()<result.length()){
//                    result = subResult;
//                }
//            }
//            left--;
//            right--;
//        }
//
//        return result;
//    }
//
    void initArray(int[] array,String s){
        for(int i=0;i<s.length();i++){
            array[s.charAt(i)-65]++;
        }
    }
//
    public static void main(String[] args){
        MinimumWindowSubstring minimumWindowSubstring = new MinimumWindowSubstring();
        System.out.println(minimumWindowSubstring.minWindow("cabwefgewcwaefgcf","cae"));
        System.out.println(minimumWindowSubstring.minWindow("bBbaBAbaAB","bbB"));
        System.out.println(minimumWindowSubstring.minWindow("babcaacabcabbbca","aaabb"));
        System.out.println(minimumWindowSubstring.minWindow("cgklivwehljxrdzpfdqsapogwvjtvbzahjnsejwnuhmomlfsrvmrnczjzjevkdvroiluthhpqtffhlzyglrvorgnalk","mqfff"));


    }

    public String minWindow(String s, String t) {
        String result = "";
        int[] sArray = new int[58];
        int[] tArray = new int[58];
        initArray(tArray,t);
        int left = 0;
        int right = 0;

        int successCount = 0;
        while (right<s.length()){
            //右指针前进
            while (successCount<t.length()&&right<s.length()){
                //如果存在 并且未满足 count++ 维护数组
                if(tArray[s.charAt(right)-65]>0 && sArray[s.charAt(right)-65]<tArray[s.charAt(right)-65]){
                    successCount++;
                }
                sArray[s.charAt(right)-65]++;
                right++;
            }
            if(successCount == t.length()){
                if(right-left<result.length()||result.equals("")){
                    result = s.substring(left,right);
                }
            }else{
                return result;
            }

            //左指针前进
            while (successCount==t.length()&& left<right){
                //如果存在 并且未满足 count++ 维护数组
                if(tArray[s.charAt(left)-65]>0 && sArray[s.charAt(left)-65]==tArray[s.charAt(left)-65]){
                    successCount--;
                }
                sArray[s.charAt(left)-65]--;
                left++;
            }
            if(successCount == t.length()-1){
                if(right-(left-1)<result.length()||result.equals("")){
                    result = s.substring(left-1,right);
                }
            }
        }

        return result;
    }
}
